package swardToOffer.struct_5_stack_or_queue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author ChanZany
 * @Date 2021/5/26 19:21
 * @Version 1.0

 面试题59（二）：队列的最大值
 题目：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，
 如果输入数组{2, 3, 4, 2, 6, 2, 5, 1}及滑动窗口的大小3，那么一共存在6个
 滑动窗口，它们的最大值分别为{4, 4, 6, 6, 6, 5}，

 解题思路:双端单调队列存储当前窗口的最大值
 该队列满足仅包含窗口内的元素 ⇒ 每轮窗口滑动移除了元素 nums[i - 1]，需将 deque内的对应元素一起删除。
deque 内的元素 非严格递减 ⇒ 每轮窗口滑动添加了元素 nums[j + 1] ，需将 deque 内所有 < nums[j + 1]的元素删除。
 */
public class MaxInSlidingWindow {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length==0||k==0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int [] res = new int[nums.length-k+1];
        //未形成窗口
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && deque.peekLast()<nums[i]) deque.removeLast();
            deque.addLast(nums[i]);
        }
        res[0]=deque.peekFirst();
        //形成窗口后
        for (int i = k; i <nums.length ; i++) {
            // 删除 deque 中对应的 nums[i-k],保证deque仅包含窗口内的元素
            if (deque.peekFirst()==nums[i-k]) deque.removeFirst();
            // 保持 deque 递减
            while (!deque.isEmpty() && deque.peekLast()<nums[i]) deque.removeLast();
            deque.addLast(nums[i]);
            // 记录窗口最大值
            res[i-k+1]=deque.peekFirst();
        }
        return res;
    }
}
